#include <stdio.h>
#include <stdlib.h>
#include <vector>
//Definition for an interval.
struct Interval {
    int start;
    int end;
    Interval() : start(0), end(0) {}
    Interval(int s, int e) : start(s), end(e) {}
};
class Solution{
public: std::vector<Interval> insert(std::vector<Interval> &intervals, Interval newInterval) {
        if (intervals.size()<=0)
        {
            intervals.insert(intervals.begin(), newInterval);
            return intervals;
        }
        std::vector<Interval>::iterator it;
        int start_index = 0;
        int start_in_or_not = 0;
        int end_index = 0;
        int end_in_or_not = 0;
        // find start
        it = intervals.begin();
        while(it < intervals.end() && (it->end) < newInterval.start)
            it++;
        start_index = it - intervals.begin();
        if ( it < intervals.end() && newInterval.start >= it->start && newInterval.start <= it->end)
        {
            start_in_or_not = 1;
        }

        while(it < intervals.end() && (it->end) < newInterval.end)
            it++;
        end_index = it - intervals.begin();
        if (it < intervals.end() && newInterval.end >= it->start && newInterval.end <= it->end)
        {
            end_in_or_not = 1;
        }
        printf("%d %d %d %d\n", start_index, end_index , start_in_or_not ,end_in_or_not);
        //none overlap
        if (start_index == end_index && start_in_or_not == 0 && end_in_or_not == 0)
        {
            intervals.insert(intervals.begin() + start_index, newInterval);
        }
        else{
            //overlap
            //1.get the newInterval
            if (start_in_or_not)
            {
                newInterval.start = intervals[start_index].start;
                printf("newInterval.start %d\n", newInterval.start);
            }

            if (end_in_or_not)
            {
                newInterval.end = intervals[end_index].end;
                printf("newInterval.end %d\n", newInterval.end);
            }
            //remove the overlaped interval
            int erase_start = start_index;
            int erase_end = end_index;
            if (end_in_or_not == 0)
            {
                erase_end -= 1;
            }
            printf("erase %d %d\n", erase_start, erase_end);
            if (erase_end >= erase_start)
            {
                intervals.erase(intervals.begin() + erase_start, intervals.begin() + erase_end + 1);
            }
            //add interval
            intervals.insert(intervals.begin() + start_index, newInterval);
        }       
        return intervals;
}
};

void printVector(std::vector<Interval> intervals)
{
    printf("Call printVector\n");
    std::vector<Interval>::iterator it;
    it = intervals.begin();
    while(it != intervals.end())
    {
        printf("start %d", it->start);
        printf("end %d\n", it->end);
        it++;
    }
}
int main(int argc, char const *argv[])
{
    std::vector<Interval> intervals;
    intervals.push_back(Interval(0, 1));
    intervals.push_back(Interval(2, 5));
    intervals.push_back(Interval(7, 8));
    intervals.push_back(Interval(13, 15));
    printVector(intervals);
    Interval newInterval = Interval(12, 14);
    printf("start %d end %d\n", newInterval.start, newInterval.end);
    Solution s;
    intervals = s.insert(intervals, newInterval);
    printVector(intervals);
    return 0;
}